The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field.[1]
Elwyn Berlekamp invented an algorithm for decoding Bose–Chaudhuri–Hocquenghem (BCH) codes.[2][3] James Massey recognized its application to linear feedback shift registers and simplified the algorithm.[4][5] Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm) (Massey 1969, p. 124), but it is now known as the Berlekamp–Massey algorithm.
Contents |
Berlekamp Massey algorithm is an alternate method to solve the set of linear equations described in Reed_Solomon_Peterson_decoder, which can be summarized as:
In the code examples below, C(x) is a potential instance of Λ(x). The error locator polynomial C(x) for L errors is defined as:
or reversed:
The goal of the algorithm is to determine the minimal degree L and C(x) which results in:
for all syndromes, n = L to (N-1).
Algorithm: C(x) is initialized to 1, L is the current number of assumed errors, and initialized to zero. N is the total number of syndromes. n is used as the main iterator and to index the syndromes from 0 to (N-1). B(x) is a copy of the last C(x) since L was updated and initialized to 1. b is a copy of the last discrepancy d (explained below) since L was updated and initialized to 1. m is the number of iterations since L, B(x), and b were updated and initialized to 1.
Each iteration of the algorithm calculates a discrepancy d. At iteration k this would be:
If d is zero, the algorithm assumes that C(x) and L are correct for the moment, increments m, and continues.
If d is not zero, the algorithm adjusts C(x) so that a recalculation of d would be zero:
The xm term shifts B(x) so it follows the syndromes corresponding to 'b'. If the previous update of L occurred on iteration j, then m = k - j, and a recalculated discrepancy would be:
This would change a recalculated discrepancy to:
The algorithm also needs to increase L (number of errors) as needed. If L equals the actual number of errors, then during the iteration process, the discrepancies will become zero before n becomes greater than or equal to (2 L). Otherwise L is updated and algorithm will update B(x), b, increase L, and reset m = 1. The L = (n + 1 - L) formula limits L to the number of available syndromes used to calculate discrepancies, and also handles the case where L increases by more than 1.
The following is the Berlekamp–Massey algorithm specialized for the typical binary finite field F2 and GF(2). The field elements are 0 and 1. The field operations + and − are identical and become the exclusive or operation, XOR. The multiplication operator * becomes the logical AND operation. The division operator reduces to the identity operation (i.e., field division is only defined for dividing by 1, and x/1 = x).
At the end of the algorithm, is the length of the minimal LFSR for the stream, and we have for all .
The following code sample is for a binary field.
public static int runTest(int[] array) { final int N = array.length; int[] b = new int[N]; int[] c = new int[N]; int[] t = new int[N]; b[0] = 1; c[0] = 1; int l = 0; int m = -1; for (int n = 0; n < N; n++) { int d = 0; for (int i = 0; i <= l; i++) { d ^= c[i] * array[n - i]; } if (d == 1) { System.arraycopy(c, 0, t, 0, N); int N_M = n − m; for (int j = 0; j < N − N_M; j++) { c[N_M + j] ^= b[j]; } if (l <= n / 2) { l = n + 1 - l; m = n; System.arraycopy(t, 0, b, 0, N); } } } return l; }
The algorithm from Massey (1969, p. 124).
polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */ /* connection polynomial */ polynomial(field K) C(x) = 1; /* coeffs are c_j */ polynomial(field K) B(x) = 1; int L = 0; int m = 1; field K b = 1; int n; for (n = 0; n < N; n++) { /* calculate discrepancy */ field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i}; if (d == 0) { /* annihilation continues */ m = m + 1; } else if (2 * L <= n) { /* temporary copy of C(x) */ polynomial(field K) T(x) = C(x); C(x) = C(x) - d b^{-1} x^m B(x); L = n + 1 - L; B(x) = T(x); b = d; m = 1; } else { C(x) = C(x) - d b^{-1} x^m B(x); m = m + 1; } } return L;